public class Solution1458 {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int[][] f=new int[nums1.length][nums2.length];
        for (int i=0;i<nums1.length;i++){
            for (int j=0;j<nums2.length;j++){
                f[i][j]=nums1[i]*nums2[j];
                for (int k=i-1;k>=0;k--){
                    f[i][j]=Math.max(f[i][j],f[k][j]);
                    if (j>0){
                        f[i][j]=Math.max(f[i][j],f[k][j-1]+nums2[j]*nums1[k+1]);
                    }
                }
                f[i][j]=Math.max(f[i][j],nums2[j]*nums1[0]);
                for (int k=j-1;k>=0;k--){
                    f[i][j]=Math.max(f[i][j],f[i][k]);
                    if (i>0){
                        f[i][j]=Math.max(f[i][j],f[i-1][k]+nums1[i]*nums2[k+1]);
                    }
                }
                f[i][j]=Math.max(f[i][j],nums1[i]*nums2[0]);
            }
        }
        return f[nums1.length-1][nums2.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1458().maxDotProduct(new int[]{2,1,-2,5},new int[]{3,0,-6}));
    }
}
